SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Cohen–Sutherland algorithm</title>

</head>

Cohen–Sutherland algorithm

</h1>

</header>

In <a href="Computer_graphics" title="Computer graphics">computer graphics</a>, the Cohen–Sutherland algorithm is an <a href="Algorithm" title="Algorithm">algorithm</a> used for <a href="Line_clipping" title="Line clipping">line clipping</a>. The algorithm divides a two-dimensional space into 9 regions and then efficiently determines the lines and portions of lines that are visible in the central region of interest (the <a href="Viewport" title="Viewport">viewport</a>).

The algorithm was developed in 1967 during <a href="Flight_simulator" title="Flight simulator">flight simulator</a> work by <a href="Danny_Cohen_(engineer)" class="mw-redirect" title="Danny Cohen (engineer)">Danny Cohen</a> and <a href="Ivan_Sutherland" title="Ivan Sutherland">Ivan Sutherland</a>.<a href="#cite_note-Sproull-1">[1]</a>

<div class="mw-heading mw-heading2"><h2 id="The_algorithm">The algorithm</h2></div>

The algorithm includes, excludes or partially includes the line based on whether:

<ul><li>Both endpoints are in the viewport region (bitwise OR of endpoints = 0000): <a href="Trivial_accept" class="mw-redirect" title="Trivial accept">trivial accept</a>.</li>

<li>Both endpoints share at least one non-visible region, which implies that the line does not cross the visible region. (bitwise AND of endpoints ≠ 0000): <a href="Trivial_reject" class="mw-redirect" title="Trivial reject">trivial reject</a>.</li>

<li>Both endpoints are in different regions: in case of this nontrivial situation the algorithm finds one of the two points that is outside the viewport region (there will be at least one point outside). The intersection of the outpoint and extended viewport border is then calculated (i.e. with the parametric equation for the line), and this new point replaces the outpoint. The algorithm repeats until a trivial accept or reject occurs.</li></ul>

The numbers in the figure below are called <a href="Outcodes_(computer_graphics)" class="mw-redirect" title="Outcodes (computer graphics)">outcodes</a>. An outcode is computed for each of the two points in the line. The outcode will have 4 bits for two-dimensional clipping, or 6 bits in the three-dimensional case. The first bit is set to 1 if the point is above the viewport. The bits in the 2D outcode represent: top, bottom, right, left. For example, the outcode 1010 represents a point that is top-right of the viewport.

<th>central</th>

<th>right

</th></tr>

<tr>

<th>top

</th>

<td>1001

</td>

<td>1000

</td>

<td>1010

</td></tr>

<tr>

<th>central

</th>

<td>0001

</td>

<td>0000

</td>

<td>0010

</td></tr>

<tr>

<th>bottom

</th>

<td>0101

</td>

<td>0100

</td>

<td>0110

</td></tr></tbody></table></dd></dl>

Note that the outcodes for endpoints must be recalculated on each iteration after the clipping occurs.

The Cohen–Sutherland algorithm can be used only on a rectangular <a href="Clip_window" class="mw-redirect" title="Clip window">clip window</a>.

<div class="mw-heading mw-heading2"><h2 id="Example_C/C++_implementation">Example C/C++ implementation</h2></div>

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>typedef int OutCode;

const int INSIDE = 0b0000;

const int LEFT = 0b0001;

const int RIGHT = 0b0010;

const int BOTTOM = 0b0100;

const int TOP = 0b1000;

// Compute the bit code for a point (x, y) using the clip rectangle

// bounded diagonally by (xmin, ymin), and (xmax, ymax)

// ASSUME THAT xmax, xmin, ymax and ymin are global constants.

OutCode ComputeOutCode(double x, double y)

{

OutCode code = INSIDE; // initialised as being inside of clip window

if (x < xmin) // to the left of clip window

code |= LEFT;

else if (x > xmax) // to the right of clip window

code |= RIGHT;

if (y < ymin) // below the clip window

code |= BOTTOM;

else if (y > ymax) // above the clip window

code |= TOP;

return code;

}

// Cohen–Sutherland clipping algorithm clips a line from

// P0 = (x0, y0) to P1 = (x1, y1) against a rectangle with

// diagonal from (xmin, ymin) to (xmax, ymax).

bool CohenSutherlandLineClip(double& x0, double& y0, double& x1, double& y1)

{

// compute outcodes for P0, P1, and whatever point lies outside the clip rectangle

OutCode outcode0 = ComputeOutCode(x0, y0);

OutCode outcode1 = ComputeOutCode(x1, y1);

bool accept = false;

while (true) {

if (!(outcode0 | outcode1)) {

// bitwise OR is 0: both points inside window; trivially accept and exit loop

accept = true;

break;

} else if (outcode0 & outcode1) {

// bitwise AND is not 0: both points share an outside zone (LEFT, RIGHT, TOP,

// or BOTTOM), so both must be outside window; exit loop (accept is false)

break;

} else {

// failed both tests, so calculate the line segment to clip

// from an outside point to an intersection with clip edge

double x, y;

// At least one endpoint is outside the clip rectangle; pick it.

OutCode outcodeOut = outcode1 > outcode0 ? outcode1 : outcode0;

// Now find the intersection point;

// use formulas:

// slope = (y1 - y0) / (x1 - x0)

// x = x0 + (1 / slope) * (ym - y0), where ym is ymin or ymax

// y = y0 + slope * (xm - x0), where xm is xmin or xmax

// No need to worry about divide-by-zero because, in each case, the

// outcode bit being tested guarantees the denominator is non-zero

if (outcodeOut & TOP) { // point is above the clip window

x = x0 + (x1 - x0) * (ymax - y0) / (y1 - y0);

y = ymax;

} else if (outcodeOut & BOTTOM) { // point is below the clip window

x = x0 + (x1 - x0) * (ymin - y0) / (y1 - y0);

y = ymin;

} else if (outcodeOut & RIGHT) { // point is to the right of clip window

y = y0 + (y1 - y0) * (xmax - x0) / (x1 - x0);

x = xmax;

} else if (outcodeOut & LEFT) { // point is to the left of clip window

y = y0 + (y1 - y0) * (xmin - x0) / (x1 - x0);

x = xmin;

}

// Now we move outside point to intersection point to clip

// and get ready for next pass.

if (outcodeOut == outcode0) {

x0 = x;

y0 = y;

outcode0 = ComputeOutCode(x0, y0);

} else {

x1 = x;

y1 = y;

outcode1 = ComputeOutCode(x1, y1);

}

return accept;

}

</pre></div>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-Sproull-1"><a href="#cite_ref-Sproull_1-0">^</a> Principles of Interactive Computer Graphics, p. 124, 252, by <a href="Bob_Sproull" title="Bob Sproull">Bob Sproull</a> and William M. Newman, 1973, McGraw–Hill Education, International edition, <style data-mw-deduplicate="TemplateStyles:r1238218222">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-07-085535-8</bdi>.

</li>

</ol></div></div>

Algorithms used for the same purpose:

<ul><li><a href="Liang%E2%80%93Barsky_algorithm" title="Liang–Barsky algorithm">Liang–Barsky algorithm</a></li>

<li><a href="Cyrus%E2%80%93Beck_algorithm" title="Cyrus–Beck algorithm">Cyrus–Beck algorithm</a></li>

<li><a href="Nicholl%E2%80%93Lee%E2%80%93Nicholl_algorithm" title="Nicholl–Lee–Nicholl algorithm">Nicholl–Lee–Nicholl algorithm</a></li>

<li><a href="Fast_clipping" class="mw-redirect" title="Fast clipping">Fast clipping</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<ul><li>James D. Foley. <a rel="nofollow" class="external text" href="https://books.google.com/books?id=-4ngT05gmAQC">Computer graphics: principles and practice</a>. Addison-Wesley Professional, 1996. p. 113.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://github.com/mapbox/lineclip">JavaScript polyline clipping library using Cohen-Sutherland algorithm</a></li>

<li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20161221235815/http://gpolo.awardspace.info/clip/main.html">Animated JavaScript implementation</a></li>

<li><a rel="nofollow" class="external text" href="https://github.com/omarreis/CohenSutherland">Delphi implementation</a></li>

<li><a rel="nofollow" class="external text" href="https://github.com/asjadnaqvi/stata-clipgeo">Stata implementation</a></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-18" href="https://en.wikipedia.org/wiki/?title=Cohen%E2%80%93Sutherland_algorithm&oldid=1296145545">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>